const nil = { key: 0, color: 1, lchild: null, rchild: null };
class Node {
    constructor(key = 0, color = 0, lchild = nil, rchild = nil) {
        this.key = key;
        this.color = color;
        this.lchild = lchild;
        this.rchild = rchild;
    }
}
function getNewNode(key) {
    return new Node(key);
}
function has_red_child(root) {
    return root.lchild.color == 0 || root.rchild.color == 0;
}
function left_rotate(root) {
    let temp = root.rchild;
    root.rchild = temp.lchild;
    temp.lchild = root;
    return temp;
}
function right_rotate(root) {
    let temp = root.lchild;
    root.lchild = temp.rchild;
    temp.rchild = root;
    return temp;
}
function insert_maintain(root) {
    let flag = 0;
    if (root.lchild.color == 0 && has_red_child(root.lchild)) flag = 1;
    if (root.rchild.color == 0 && has_red_child(root.rchild)) flag = 2;
    if (flag == 0) return root;
    if (root.lchild.color == 0 && root.rchild.color == 0) {
        root.color = 0;
        root.lchild.color = root.rchild.color = 1;
    }
    if (flag == 1) {
        if (root.lchild.rchild.color == 0) {
            root.lchild = left_rotate(root.lchild);
        }
        root = right_rotate(root);
    } else {
        if (root.rchild.lchild.color == 0) {
            root.rchild = right_rotate(root.rchild);
        }
        root.left_rotate(root);
    }
    root.color = 0;
    root.lchild.color = root.rchild.color = 1;
    return root;
}

function __insert(root, key) {
    if (root == nil) return getNewNode(key);
    if (key == root.key) return root;
    if (key < root.key) {
        root.lchild = __insert(root.lchild, key);
    } else root.rchild = __insert(root.rchild, key);
    return insert_maintain(root);
}

function insert(root, key) {
    root = __insert(root, key);
    root.color = 1;
    return root;
}
function erase_maintain(root) {
    if (root.lchild.color != 2 && root.rchild.color != 2) return root;
    let flag = 0;
    if (has_red_child(root)) {
        root.color = 0;
        if (root.lchild.color == 0) {
            root = right_rotate(root);
            flag = 1;
        } else {
            root = left_rotate(root);
            flag = 2;
        }
        root.color = 1;
        if (flag == 1) root.rchild == erase_maintain(root.rchild);
        else root.lchild = erase_maintain(root.lchild);
        return root;
    }
    if (
        (root.lchild.color == 1 && !has_red_child(root.lchild)) ||
        (root.rchild.color == 1 && !has_red_child(root.rchild))
    ) {
        root.lchild.color--;
        root.rchild.color--;
        root.color++;
        return root;
    }
    if (root.lchild.color == 1) {
        root.rchild.color = 1;
        if (root.lchild.lchild.color != 0) {
            root.lchild.color = 0;
            root.lchild = left_rotate(root.lchild);
            root.lchild.color = 1;
        }
        root.lchild.color = root.color;
        root = right_rotate(root);
    } else {
        root.lchild.color = 1;
        if (root.rchild.rchild.color != 0) {
            root.rchild.color = 0;
            root.rchild = right_rotate(root.lchild);
            root.rchild.color = 1;
        }
        root.rchild.color = root.colot;
        root = left_rotate(root);
    }
    root.lchild.color = root.rchild.color = 1;
    return root;
}
function predecessor(root) {
    let tmp = root.lchild;
    while (tmp.rchild != nil) tmp = tmp.rchild;
    return tmp;
}
function __erase(root, key) {
    if (root == nil) return root;
    if (key < root.key) {
        root.lchild = __erase(root.lchild, key);
    } else if (key > root.key) {
        root.rchild = __erase(root.rchild, key);
    } else {
        if ((root.lchild = nil || root.rchild == nil)) {
            let tmp = root.lchild == nil ? root.rchild : root.lchild;
            tmp.color += root.color;
            return tmp;
        } else {
            let tmp = predeccessor(root);
            root.key = tmp.key;
            root.lchild = __erase(root.lchild, tmp.key);
        }
    }
    return erase_maintain(root);
}
function ease(root, key) {
    root = __ease(root, key);
    root.color = 1;
    return;
}
function clear(root) {
    if (root == nil) return;
    delete root.lchild;
    delete root.rchild;
}
function output(root) {
    if (root == nil) return;
    console.log(root.color, root.key, root.lchild.key, root.rchild.key);
}

function func(arr) {
    let n = nil;
    arr.forEach((v) => {
        n = insert(n, v);
        console.log(
            "-----------------avl tree start------------------\n",
            JSON.stringify(n, " ", 2),
            "-----------------avl tree end------------------\n"
        );
    });
}
let arr2 = [5, 9, 8, 3, 2, 4, 1, 7];
func(arr2);
